package com.practice.niuke.new_direct_practice.class27;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

/**
 * 给定一个只含0和1二维数组matrix，第0行表示天花板。每个位置认为与上、下、左、右四个方
 * 向有粘性，比如：
 * matrix =
 * 1 0 0 1 0
 * 1 0 0 1 1
 * 1 1 0 1 1
 * 1 0 0 0 0
 * 0 0 1 1 0
 * 注意到0行0列是1，然后能延伸出5个1的一片。同理0行3列也是1，也能延伸出5个1的一片。注
 * 意到4行2列是1，然后能延伸出2个1的一片。其中有两片1是粘在天花板上的，而4行2列延伸出
 * 来的这片，认为粘不住就掉下来了。
 * 在给定一个二维数组bomb，表示炸弹的位置，比如：
 * bomb =
 * 2 0
 * 1 3
 * 1 4
 * 0 3
 * 第一枚炮弹在2行0列，该处的1直接被打碎，然后会有2个1掉下来。
 * 第二枚炮弹在1行3列，该处的1直接被打碎，不会有1掉下来，因为这一片1还能粘在一起。
 * 第三枚炮弹在1行4列，该处的1直接被打碎，然后会有2个1掉下来。
 * 第四枚炮弹在0行3列，该处的1直接被打碎，不会有1掉下来，因为这一片1只剩这一个了。
 * 根据matrix和bomb，返回结果[2,0,2,0]。
 */
public class Code02_BricksFallingWhenHit1 {

    /**
     * 每一个1都有一个专属于自己的Dot
     */
    public static class Dot {

    }

    public static class UnionFind {
        // 原始数组，经过炮弹的影响之后，所得到的数组就是grid数组
        private int[][] grid; // 主函数处理后的原始矩阵
        // 行数
        private int N;
        // 列数
        private int M;
        // 目前为止，有多少个1能连接到天花板
        private int cellingAll;
        // 让每个1都有自己特定的Dot
        private Dot[][] dots; // 位置到点的对应关系
        // 新增的数据结构：某个集合，是不是整体接到天花板上去了，
        // 如果是，假设这个集合的代表点为x，那么cellingSet就包含x；
        // 如果不是，假设这个集合的代表点为x，那么cellingSet就不包含x
        private HashSet<Dot> cellingSet; // 集合能够连到天花板，它的代表点才在里面
        // 任何一个dot都有记录，value就是父节点
        private HashMap<Dot, Dot> fatherMap;
        // 记录每一个代表节点，代表的集合的大小
        private HashMap<Dot, Integer> sizeMap;
        // 只有一个dot是代表点，才有记录，value表示这个集合的大小

        public UnionFind(int[][] matrix) {
            initSpace(matrix);
            initConnect();
        }

        // 初始化并查集
        private void initSpace(int[][] matrix) {
            grid = matrix;
            N = grid.length;
            M = grid[0].length;
            // 目前为止，接到天花板上砖的数量为0
            cellingAll = 0;
            dots = new Dot[N][M]; // dot null
            cellingSet = new HashSet<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for (int row = 0; row < N; row++) {
                for (int col = 0; col < M; col++) {
                    // 遍历每一个[i][j]，2、0直接跳过
                    if (grid[row][col] == 1) { // 该点是我关心的，不是1就不关心
                        Dot cur = new Dot();
                        dots[row][col] = cur;
                        fatherMap.put(cur, cur);
                        sizeMap.put(cur, 1);
                        if (row == 0) { // dot是天花板上的点
                            cellingSet.add(cur);
                            cellingAll++;
                        }
                    }


                }
            }
        }

        // 集合的初始化合并（连通）
        private void initConnect() {
            for (int row = 0; row < N; row++) {
                for (int col = 0; col < M; col++) {
                    union(row, col, row - 1, col);
                    union(row, col, row + 1, col);
                    union(row, col, row, col - 1);
                    union(row, col, row, col + 1);
                }
            }
        }

        // row，col  的dot，所在的集合，代表dot是谁返回
        private Dot find(int row, int col) {
            Dot cur = dots[row][col];
            Stack<Dot> stack = new Stack<>();
            while (cur != fatherMap.get(cur)) {
                stack.add(cur);
                cur = fatherMap.get(cur);
            }
            while (!stack.isEmpty()) {
                fatherMap.put(stack.pop(), cur);
            }
            return cur;
        }

        // 如果[r1][c1]的位置上是1，并且[r2][c2]位置上也是1，则合并；否则什么也不干
        private void union(int r1, int c1, int r2, int c2) {
            if (valid(r1, c1) && valid(r2, c2)) {
                Dot father1 = find(r1, c1);
                Dot father2 = find(r2, c2);
                if (father1 != father2) {

                    int size1 = sizeMap.get(father1);
                    int size2 = sizeMap.get(father2);
                    // 集合1整体连不连得到天花板上
                    boolean status1 = cellingSet.contains(father1);
                    // 集合2整体连不连得到天花板上
                    boolean status2 = cellingSet.contains(father2);
                    if (size1 <= size2) {
                        // 集合1与集合2，已经合并完了，共同的父节点father2
                        fatherMap.put(father1, father2);
                        sizeMap.put(father2, size1 + size2);
                        sizeMap.remove(father1);
                        // 如果两个集合能否接到天花板的状态不一样
                        if (status1 ^ status2) {
                            cellingSet.add(father2);
                            cellingAll += status1 ? size2 : size1;
                        }
                    } else {
                        fatherMap.put(father2, father1);
                        sizeMap.put(father1, size1 + size2);
                        if (status1 ^ status2) {
                            cellingSet.add(father1);
                            cellingAll += status1 ? size2 : size1;
                        }
                    }


                }
            }
        }

        // 检查有效性，不越界且位置上是1，则检查通过
        private boolean valid(int row, int col) {
            return row >= 0 && row < N && col >= 0 && col < M && grid[row][col] == 1;
        }

        public int cellingNum() {
            return cellingAll;
        }

        /**
         * 原来[row][clo]位置是2，将其变为1后，接到天花板上的数量是否有变化，如果有变化，返回掉落的砖块数量
         *
         * @param row
         * @param col
         * @return
         */
        public int finger(int row, int col) {
            grid[row][col] = 1;
            Dot cur = new Dot();
            dots[row][col] = cur;
            if (row == 0) {
                cellingSet.add(cur);
                cellingAll++;
            }
            fatherMap.put(cur, cur);
            sizeMap.put(cur, 1);
            int pre = cellingAll;
            union(row, col, row - 1, col);
            union(row, col, row + 1, col);
            union(row, col, row, col - 1);
            union(row, col, row, col + 1);
            int now = cellingAll;
            if (row == 0) {
                return now - pre;
            } else {
                return now == pre ? 0 : now - pre - 1;
            }
        }
    }

    /**
     * TODO: 主方法
     *
     * @param grid 原始矩阵数组
     * @param hits 炮弹二维数组，hits[n][2]
     * @return
     */
    public static int[] hitBricks(int[][] grid, int[][] hits) {
        // 把炮弹的影响加上原始矩阵数组grid会怎么变
        for (int i = 0; i < hits.length; i++) {
            // 将原始矩阵数组中炮弹打中位置是1的位置，改为2
            if (grid[hits[i][0]][hits[i][1]] == 1) {
                grid[hits[i][0]][hits[i][1]] = 2;
            }
        }
        // 初始化并查集
        UnionFind unionFind = new UnionFind(grid);
        int[] ans = new int[hits.length];
        // 从最晚到最早的炮弹，逆时序回溯求解
        for (int i = hits.length - 1; i >= 0; i--) {
            // 原来是1，现在是2的地方，就是炮弹有效打中的地方
            if (grid[hits[i][0]][hits[i][1]] == 2) {
                ans[i] = unionFind.finger(hits[i][0], hits[i][1]);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 0, 1}, {1, 1, 1}};
        int[][] hits = {{0, 0}, {0, 2}, {1, 1}};
        int[] ans = hitBricks(grid, hits);
        for (int i = 0; i < ans.length; i++) {
            System.out.println(ans[i]);
        }
    }

}
